package com.tgy.algorithm.sort;

import java.util.Arrays;

public class QuickSort01 {


    public static void quickSort(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return;
        }
        doQuickSort(nums,0, nums.length - 1);
    }

    public static void doQuickSort(int[] nums,int left, int right) {

        if (left >= right) {
            return;
        }

        int[] range = findRange(nums,left,right);
        doQuickSort(nums,left,range[0] - 1);
        doQuickSort(nums,range[1]+1,right);
    }

    public static int[] findRange(int[] nums,int left, int right) {

        int[] rets = new int[2];

        int leftIndex = left - 1;
        int rightIndex = right - 1;
        int index = left;
        int value = nums[right];

        while (index <= rightIndex) {
            if (nums[index] < value) {
                if (leftIndex + 1 != index) {
                    swap(nums,leftIndex+1,index);
                }
                leftIndex++;
                index++;
            }else if (nums[index] > value) {
                swap(nums,index,rightIndex);
                rightIndex--;
            }else {
                index++;
            }
        }
        swap(nums,rightIndex+1,right);
//        System.out.println( value + ":" +Arrays.toString(nums));
        rets[0] = leftIndex+1;
        rets[1] = rightIndex+1;
        return rets;
    }

    public static void swap(int[] nums ,int one ,int two) {
        int tmp = nums[one];
        nums[one] = nums[two];
        nums[two] = tmp;
    }

    public static void main(String[] args) {
        // [-46, -7, 20, 16, -46, -22, 13, -25]
//        int[] nums = new int[]{3,2,1,2,4,3,2};
        int[] nums = new int[]{-46, -7, 20, 16, -46, -22, 13, -25};
        quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
